74. 搜索二维矩阵

// 编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：
// 每行中的整数从左到右按升序排列。
// 每行的第一个整数大于前一行的最后一个整数。
var searchMatrix = function(matrix, target) {
  const m = matrix.length,
    n = matrix[0].length;
  let is = true, // 表示是否从左到右升序并且每行的第一个整数大于前一行的最后一个整数。
    has = false; // 表示target是否存在
  for (let i = 0; i < m; i++) {
    // 外层循环, 判断每行的第一个整数大于前一行的最后一个整数。
    if (i > 0 && matrix[i][0] < matrix[i - 1][n - 1]) {
      is = false;
      break;
    }

    // 判断内层数组长度是否大于1, 如果不大于一, 则不需要判断升序, 只需要判断target是否存在即可
    // 如果大于一, 则需要判断是否是升序, 同时也要判断是否存在target
    if (n > 1) {
      for (let j = 0; j < n - 1; j++) {
        if (matrix[i][j] > matrix[i][j + 1]) {
          is = false;
          break;
        }
        if (!has) {
          has = matrix[i][j] === target;
          if (j === n - 2 && !has) has = matrix[i][j + 1] === target;
        }
      }
    } else {
      if (!has) {
        has = matrix[i][0] === target;
      }
    }
  }

  return is && has;
};
// console.log(
//   searchMatrix(
//     [
//       [1, 3, 5, 7],
//       [10, 11, 16, 20],
//       [23, 30, 34, 60],
//     ],
//     3
//   )
// ); // true
// console.log(
//   searchMatrix(
//       [
//         [1, 3, 5, 7],
//         [10, 11, 16, 20],
//         [23, 30, 34, 60],
//       ],
//     ,
//     13
//   )
// ); // true
console.log(searchMatrix([[1]], 1)); // true
console.log(searchMatrix([[1, 3]], 1)); // true
console.log(searchMatrix([[1, 3, 5]], 5)); // true